Online-Academy
Look, Read, Understand, Apply

Data Structure

B tree

B Tree

A B Tree is multiway search tree having order m, m indicates how many children a node will have. B tree has following properties:

  • If root is not leaf, it has at least two subtrees.
  • Each intermediate node hold k - 1 keys and k references to subtrees where ceiling(m/2) <= k <=m.
  • Each leaf node has k-1 keys where ceiling(m/2) <= k <=m
  • All the leaves are in same level.

B Tree Node

        class BTreeNode{
            int m, int numberofkeys;
            boolean leaf = true;
            int keys[];
            BTreeNode references[];
            BTreeNode(int m, int n, int key){
                this.m = m;
                this.numberofkeys = n;
                keys = new int[m-1];
                references = new BTreeNode[m];
                keys[0] = key;
                for(int i=0;i<m;i++)
                    references[i] = null;
            }
        }

Algorithm to insert keys in B-trees:

        BTreeInsert(key){
            find a leaf node to insert key;
            while(true){
                find a proper position in found leaf node for key;
                if node is have empty space{
                    insert key and increment numberofkeys;
                    return;
                }else{
                    split node into two nodes: n1 and n2, n1 = node and n2 is new one; 
                    distribute keys and references between n1 and n2 without violating definition of B Tree, initialize numberofkeys correctly;
                    key = the last key of n1; 
                    if node is root{
                        create a new root node as parent of n1 and n2;
                        put key and references to n1 and n2 in the root, set it numberofkeys to 1;
                        return; 
                    }else{
                        node = its parent; 
                    }
                }

            }
        }